
package com.leetcode.根据算法进行分类.滑动窗口相关;

/**
 * @author: xiaomi
 * @date: 2021/2/10
 * @description: 567. 字符串的排列
 * https://leetcode-cn.com/problems/permutation-in-string/
 * 当我从 left 发现作为最优先的时候，就会出现【不断试探 right ，并且 left 不能固定的问题！】
 * 所以，必须要换个思路！
 * 因为当我确定边界的时候，必须固定！除非做下一轮循环了，才能放开该固定！
 */
public class B_567_字符串的排列 {

	public static void main(String[] args) {
		B_567_字符串的排列 action = new B_567_字符串的排列();
		test1(action);
		test2(action);
		test3(action);
		test4(action);
		test5(action);
		test6(action);
	}


	public static void test1(B_567_字符串的排列 action) {
		// 1
		String s1 = "ab";
		String s2 = "eidbaooo";
		boolean res = action.checkInclusion(s1, s2);
		res = action.checkInclusionByLeft(s1, s2);
		System.out.println("res = " + res);
	}

	public static void test2(B_567_字符串的排列 action) {
		// 0
		String s1 = "ab";
		String s2 = "eidboaoo";
		boolean res = action.checkInclusion(s1, s2);
		res = action.checkInclusionByLeft(s1, s2);
		System.out.println("res = " + res);
	}

	public static void test3(B_567_字符串的排列 action) {
		// 1
		String s1 = "adc";
		String s2 = "dcda";
		boolean res = action.checkInclusion(s1, s2);
		res = action.checkInclusionByLeft(s1, s2);
		System.out.println("res = " + res);
	}

	public static void test4(B_567_字符串的排列 action) {
		// 1
		String s1 = "ab";
		String s2 = "ab";
		boolean res = action.checkInclusion(s1, s2);
		res = action.checkInclusionByLeft(s1, s2);
		System.out.println("res = " + res);
	}

	public static void test5(B_567_字符串的排列 action) {
		// 1
		String s1 = "abc";
		String s2 = "bbbca";
		boolean res = action.checkInclusion(s1, s2);
		res = action.checkInclusionByLeft(s1, s2);
		System.out.println("res = " + res);
	}

	public static void test6(B_567_字符串的排列 action) {
		// 0
		String s1 = "hello";
		String s2 = "ooolleoooleh";
		boolean res = action.checkInclusion(s1, s2);
		res = action.checkInclusionByLeft(s1, s2);
		System.out.println("res = " + res);
	}

	/**
	 * 这个是官方题解，固定 right 的思路！！！
	 * @param s1
	 * @param s2
	 * @return
	 */
	private boolean checkInclusion(String s1, String s2) {
		return false;
	}


	/**
	 * 这个写法太复杂了，看来我还是木有考虑清楚！
	 * @param s1
	 * @param s2
	 * @return
	 */
	public boolean checkInclusionFail(String s1, String s2) {
		//用数组记录 小写字母的位置
		int[] arr = new int[26];
		char[] chars1 = s1.toCharArray();
		char[] chars2 = s2.toCharArray();
		int len1 = chars1.length;
		int len2 = chars2.length;
		//将 chars1 的信息进行记录
		for (int i = 0; i < len1; i++) {
			arr[chars1[i] - 'a']++;
		}
		//做一个副本
		int[] copyArr = new int[26];
		//做一个 s2 的中间计算保存结果：value=index
		int[] s2IndexArr = new int[len2];
		int begin = 0, end = 0, index = 0;
		int size = len2 - len1 + 1;
		//记录已经平复的 index 的数量
		int okSize = 0;
		while (begin < size) {
			//拷贝副本
			System.arraycopy(arr, 0, copyArr, 0, 26);
			index = chars2[begin] - 'a';
			while (begin < size && copyArr[index] == 0) {
				//进行记录
				s2IndexArr[begin] = index;
				begin++;
				index = chars2[begin] - 'a';
			}
			if (begin == size) {
				//如果找遍了都木有交集->
				return false;
			}
			//此时 begin 的位置处 开始 与 s1 有了交集
			s2IndexArr[begin] = index;
			copyArr[index]--;

			end = begin + 1;
			while (end < len2 && copyArr[chars2[end] - 'a'] > 0){
				copyArr[chars2[end] - 'a']--;
				end++;
			}

			//用 arr[index] 是否破界来判断是否完成遍历
			//此时 endIndex 的位置 < 0
			int l = end - begin ;
			if (l == len1) {
				return true;
			}
			while (l < len1) {
				//恢复 begin
				copyArr[s2IndexArr[begin]]++;
				begin++;
				while (end< len2 && copyArr[chars2[end] - 'a'] > 0) {
					copyArr[index]--;
					l = end - begin + 1;
					if (l == len1) {
						return true;
					}
					end++;
				}
				if (end==len2){
					return false;
				}
				//准备进入下一个循环
				begin = end;
				break;
			}
		}
		return false;
	}


	/**
	 * 可能是我想一口吃成个胖子了...
	 * 我先写个 O(n^2) 的吧
	 * --
	 * 如果我先写出来个 O(n^2) 的并且能通过是最稳妥的。
	 * 然后再考虑优化：如果不能固定 left 就固定  right !
	 * 结果我想一蹴而就，就把自己绕死了！！！
	 * @param s1
	 * @param s2
	 * @return
	 */
	public boolean checkInclusionByLeft(String s1, String s2) {
		//用数组记录 小写字母的位置
		int[] arr = new int[26];
		char[] chars1 = s1.toCharArray();
		char[] chars2 = s2.toCharArray();
		int len1 = chars1.length;
		int len2 = chars2.length;
		//将 chars1 的信息进行记录
		for (int i = 0; i < len1; i++) {
			arr[chars1[i] - 'a']++;
		}
		//做一个副本
		int[] copyArr = new int[26];
		int begin = 0, end = 0;
		int size = len2 - len1 + 1;
		while (begin < size) {
			//拷贝副本
			System.arraycopy(arr, 0, copyArr, 0, 26);
			while (begin < size && copyArr[chars2[begin] - 'a'] == 0) {
				//进行记录
				begin++;
			}
			if (begin == size) {
				//如果找遍了都木有交集->
				return false;
			}
			//此时 begin 的位置处 开始 与 s1 有了交集
			copyArr[chars2[begin] - 'a']--;

			end = begin + 1;
			while (end < len2 && copyArr[chars2[end] - 'a'] > 0){
				copyArr[chars2[end] - 'a']--;
				end++;
			}

			//用 arr[index] 是否破界来判断是否完成遍历
			//此时 endIndex 的位置 < 0
			int l = end - begin ;
			if (l == len1) {
				return true;
			}
			begin++;
		}
		return false;
	}
}
